/**
 * @file complete_binary_tree.hpp
 * @author 逆流 (1171267147@qq.com)
 * @brief 完全二叉树: 除了最后一层外，每一层都被完全填满，最后一层的节点尽可能地靠左排列
 * @version 0.1
 * @date 2024-10-15
 *
 * @copyright Copyright (c) 2024
 *
 */

#ifndef INC_STL_COMPLETE_BINARY_TREE_HPP_
#define INC_STL_COMPLETE_BINARY_TREE_HPP_

#include <cassert>
#include <iostream>

#include "binary_tree.hpp"

namespace stl {

template <typename T>
class CompleteBinaryTree : public BinaryTree<T> {
public:
    CompleteBinaryTree() {
        data_       = new BinaryTreeNode<T>[max_size_];
        this->root_ = data_;
        this->size_ = 0;
        assert(this->root_ != nullptr);
    }

    ~CompleteBinaryTree() {
        delete[] data_;
        data_       = nullptr;
        this->root_ = nullptr;
        this->size_ = 0;
    }

    void Push(T data) override {
        if (this->size_ >= max_size_) {
            std::cout << "CompleteBinaryTree is full" << '\n';
            return;
        }
        data_[this->size_].data = data;
        if (this->size_ > 0) {
            auto parent = (this->size_ - 1) / 2;
            if (this->size_ % 2 != 0) {
                this->root_[parent].left = &data_[this->size_];
            } else {
                this->root_[parent].right = &data_[this->size_];
            }
        }
        this->size_++;
    }

    T Pop() override {
        if (this->Empty()) {
            throw std::out_of_range("CompleteBinaryTree is empty!");
        }
        auto data = data_[this->size_].data;
        if (this->size_ > 0) {
            auto parent = (this->size_ - 1) / 2;
            if (this->size_ % 2 != 0) {
                data_[parent].left = nullptr;
            } else {
                data_[parent].right = nullptr;
            }
        }
        this->size_--;
        return data;
    }

    void Clear() override {
        delete[] data_;
        data_       = nullptr;
        this->root_ = nullptr;
        this->size_ = 0;
    }

private:
    BinaryTreeNode<T> *data_     = nullptr;
    std::size_t        max_size_ = 1024;
};
}  // namespace stl

#endif  // INC_STL_COMPLETE_BINARY_TREE_HPP_
